﻿// next_greater_element.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int>my_map;
        stack<int>st;       

        int size2 = nums2.size();
        for (int i = size2 - 1; i >= 0; i--)
        {
            int curr = nums2[i];
            while (!st.empty() &&  curr >= st.top())
            {
                st.pop();
            }

            if (st.empty()) my_map[curr] = -1;
            else my_map[curr] = st.top();

            st.push(curr);
        }

        vector<int>result;
        for (int i = 0; i < nums1.size(); i++)
        {
            int curr = nums1[i];
            result.push_back(my_map[curr]);
        }

        return result;
    }

    
    string removeOuterParentheses(string s) {
        stack<int>my_st;
        string result;
        for (auto& s_char : s)
        {
            if (s_char == ')')
            {
                my_st.pop();
            }
            if (!my_st.empty())
            {
                result += s_char;
            }
            if (s_char == '(')
            {
                my_st.push(s_char);
            }
        }
        return result;
        //------
    }

};

class StockSpanner {
public:
    stack<int>st;
    map<int, int>mmap;
    StockSpanner() {

    }

    int next(int price) {
        int result = 1;
        while (!st.empty() && price >= st.top())
        {
            result+=mmap[st.top()];
            
            st.pop();
        }
        mmap[price] = result;
        st.push(price);

        return result;
    }
};

int main()
{

    {
        //(()())(())
        string str = "((()))";
        Solution solu;
        string result = solu.removeOuterParentheses(str);
        cout << result;
    }

    {
        //小于或等于今天价格的最大连续日数
        //[100,80,60,70,60,75,85] [1,1,1,2,1,4,6]
        /*
        1112123
        1112146 stack{60,70,80,100}
        */
        StockSpanner stockSpan;
        stockSpan.next(100);
        stockSpan.next(80);
        stockSpan.next(60);
        stockSpan.next(70);
        stockSpan.next(60);
        stockSpan.next(75);
        stockSpan.next(85);
        return 0;
    }

    vector<int>nums1 = { 4, 1, 2 };
    vector<int>nums2 = { 1, 3, 4, 2 };

    Solution solu;
    vector<int>result = solu.nextGreaterElement(nums1, nums2);
    for (auto& item : result)
    {
        cout << item << ' ';
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
